package org.raymond.iworks.study.basic.structure.recursion;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 迷宫问题(回溯),递归:
 * 递归是方法自己调用自己,每次调用时传入不同的变量.
 * 递归有助于解决复杂的问题,同时可以让代码变得简洁.
 * 递归可以解决的问题:
 * 1) 数学问题: 8皇后,汉诺塔,阶乘,迷宫,球和篮子问题(google编程大赛)
 * 2) 算法:快排,归并排序,二分查找,分治算法等
 * 3) 将用栈解决的问题换成用递归解决,代码会更简洁一些
 * 递归需要遵守的规则:
 * 1) 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
 * 2) 方法的局部变量是独立的,不会互相影响
 * 3) 递归必须向退出递归的条件逼近,否则就是无限递归
 * 4) 当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁.
 */
public class RecursionTest {
    public static void main(String[] args) {
        //simpleTest2(4);
        int res = factorial(3);
        System.out.println("res="+res);
    }

    public static void simpleTest1(int n){
        if(n>2){
            // 参数必须有变化,否则会陷入死循环
            simpleTest1(n-1);
        }
        // 直到最深处后逐个回溯,因此会逆序执行
        System.out.println("n="+n);
    }

    public static void simpleTest2(int n){
        if(n>2){
            // 参数必须有变化,否则会陷入死循环
            simpleTest2(n-1);
        }else {
            // 直到最深处后只打印一次,回溯到上一次调用时都会被else档掉,不再执行
            System.out.println("n=" + n);
        }
    }

    //阶乘问题
    public static int factorial(int n){
        if(n==1){
            return 1;
        }else {
            return factorial(n-1)*n;
        }
    }
}
